<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="UTF-8">
	<title>Title</title>
</head>
<body>
<script>
	/*
	* 题目： 给定一个数组nums，判断 nums 中是否存在三个元素a，b，c，使得 a + b + c = target，找出所有满足条件且不重复的三元组合
	* 输入： nums: [5, 2, 1, 1, 3, 4, 6] ；target:0
	* [[1, 1, 6], [1, 2, 5], [1, 3, 4]]
	* */

	/*
	* 解题思路：
		1、特判，对于数组长度 nnn，如果数组为 null 或者数组长度小于 333，返回 []。
		2、对数组进行排序。
		3、遍历排序后数组：
			- 若 nums[i]>0nums[i]>0nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 000，直接返回结果。
			- 对于重复元素：跳过，避免出现重复解
			- 令左指针 L=i+1L=i+1L=i+1，右指针 R=n−1R=n-1R=n−1，当 L<RL<RL<R 时，执行循环：
				. 当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L,RL,RL,R 移到下一位置，寻找新的解
				. 若和大于 000，说明 nums[R]nums[R]nums[R] 太大，RRR 左移
				. 若和小于 000，说明 nums[L]nums[L]nums[L] 太小，LLL 右移
	* */
	function threeSum(arr) {
		let ans = []
		const lens = arr.length
		if (lens < 3) return ans
		arr.sort((a, b) => a - b)
		for (let i = 0; i < lens; i++) {
			if (arr[i] > 0) break
			if (i > 0 && arr[i] === arr[i-1])continue
			let L = i+1
			let R = lens - 1
			while (L < R) {
				const sum = (arr[i] + arr[L] + arr[R])
				if (sum === 0) {
					ans.push([arr[i], arr[L], arr[R]])
					while(arr[L] === arr[L+1]) L++
					while(arr[R] === arr[R-1]) R--
					L++
					R--
				}else if(sum < 0) {
					L++
				}else if(sum > 0) {
					R--
				}
			}
		}
		return ans
	}
	let val = threeSum([3,-3,-3,0,4,4,-2,-2,-1,7,5,-13,-6])
	console.log('val',val)


	// 官方示例
	/**
	 * @param {number[]} nums
	 * @return {number[][]}
	 */
	var threeSum = function(nums) {
		let ans = [];
		const len = nums.length;
		if(nums == null || len < 3) return ans;
		nums.sort((a, b) => a - b); // 排序
		for (let i = 0; i < len ; i++) {
			if(nums[i] > 0) break; // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
			if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
			let L = i+1;
			let R = len-1;
			while(L < R){
				const sum = nums[i] + nums[L] + nums[R];
				if(sum == 0){
					ans.push([nums[i],nums[L],nums[R]]);
					while (L<R && nums[L] == nums[L+1]) L++; // 去重
					while (L<R && nums[R] == nums[R-1]) R--; // 去重
					L++;
					R--;
				}
				else if (sum < 0) L++;
				else if (sum > 0) R--;
			}
		}
		return ans;
	}
</script>

</body>
</html>